//by concyclics
//create on 2021/09/02
//
//
//template of binary index tree
//
//
//my blogs https://blog.csdn.net/qq_21008741
//concyclics@github https://github.com/Concyclics
//concyclics@gitee https://gitee.com/concyclics
#include <iostream>

//define of the binary index tree
template <class T=int>
class BinaryIndexTree
{
    public:
    //create binary index tree
    //from 1 to n [1,n]
    BinaryIndexTree(const int n,const T value=0)
    {
        if(n<1)
        {
            throw std::range_error("input size error!");
        }
        
        num = new T[n+1];
        len=n;
        initValue=value;
        
        clear();

    }
    
    //add element: element position
    //false means failure, true means success.
    bool add(const T element,const int position)
    {
        if(position>len||position<1)
        {
            return false;
        }
        
        for(int i=position;i<=len;i+=lowbit(i))
        {
            num[i]+=element;

        }
        
        return true;
    }
    
    
    // from 0 to n [1,n]
    T getsum(const int n)
    {
        if(n>len||n<0)
        {
            throw std::range_error("out of size!");
        }
        
        T sum=initValue;
        for(int i=n;i>0;i-=lowbit(i))
        {
            sum+=num[i];
        }
        
        return sum;
    }
    
    //from l to r [l,r]
    T getsum(const int l, const int r)
    {
        if(l>r)
        {
            throw std::range_error("r must greater than l!");
        }
        
        return getsum(r)-getsum(l-1);
    }
    
    //get single element
    T operator[] (const int n)
    {
        if(n>len||n<1)
        {
            throw std::range_error("out of size!");
        }
        else
        {
            return getsum(n,n);
        }
    }
    
    //get size
    int size()
    {
        return len;
    }
    
    //clear
    void clear()
    {
        for(int i=0;i<=len;i++)
        {
            num[i]=initValue;
        }
    }
    
    
    private:
    //data
    T* num;
    //size of tree
    int len;
    T initValue;
    
    //lowbit
    int lowbit(int x)
    {
        return x&(-x);
    }
    
};